SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Automatic sequence</title>

</head>

Automatic sequence

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For the phonograph record property, see <a href="Automatic_sequencing" class="mw-redirect" title="Automatic sequencing">Automatic sequencing</a>.</div>

In <a href="Mathematics" title="Mathematics">mathematics</a> and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite <a href="Sequence" title="Sequence">sequence</a> of terms characterized by a <a href="Finite_automaton" class="mw-redirect" title="Finite automaton">finite automaton</a>. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed <a href="Radix" title="Radix">base</a> k.<a href="#cite_note-as1-1">[1]</a><a href="#cite_note-BLRS78-2">[2]</a>

An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS(n) is k-automatic, where χS(n) = 1 if n <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \in }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \in }</annotation>

</semantics>

</math><img src="./6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:1.843ex;" alt="{\displaystyle \in }" loading="lazy"> S and 0 otherwise.<a href="#cite_note-3">[3]</a><a href="#cite_note-PF13-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Automatic sequences may be defined in a number of ways, all of which are equivalent. Four common definitions are as follows.

<div class="mw-heading mw-heading3"><h3 id="Automata-theoretic">Automata-theoretic</h3></div>

Let k be a positive <a href="Integer" title="Integer">integer</a>, and let D = (Q, Σk, δ, q0, Δ, τ) be a <a href="Deterministic_finite_automaton" title="Deterministic finite automaton">deterministic finite automaton</a> with output, where

<ul><li>Q is the finite <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of states;</li>

<li>the input alphabet Σk consists of the set {0,1,...,k-1} of possible digits in <a href="Radix" title="Radix">base</a>-k notation;</li>

<li>δ : Q × Σk → Q is the transition function;</li>

<li>q0 ∈ Q is the initial state;</li>

<li>the output alphabet Δ is a finite set; and</li>

<li>τ : Q → Δ is the output function mapping from the set of internal states to the output alphabet.</li></ul>

Extend the transition function δ from acting on single digits to acting on strings of digits by defining the action of δ on a string s consisting of digits s1s2...st as:

Define a function a from the set of positive integers to the output alphabet Δ as follows:

where s(n) is n written in base k. Then the sequence a = a(1)a(2)a(3)... is a k-automatic sequence.<a href="#cite_note-as1-1">[1]</a>

An automaton reading the base k digits of s(n) starting with the most significant digit is said to be direct reading, while an automaton starting with the least significant digit is reverse reading.<a href="#cite_note-PF13-4">[4]</a> The above definition holds whether s(n) is direct or reverse reading.<a href="#cite_note-PF15-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="Substitution">Substitution</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy"> be a k-<a href="Uniform_morphism" class="mw-redirect" title="Uniform morphism">uniform morphism</a> of a <a href="Free_monoid" title="Free monoid">free monoid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{*}}</annotation>

</semantics>

</math><img src="./807344600a40f1de7136f8b54576e12e9428bef4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.732ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{*}}" loading="lazy"> and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> be a coding (that is, a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">-uniform morphism), as in the automata-theoretic case. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> is a <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed point</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy">—that is, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=\varphi (w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=\varphi (w)}</annotation>

</semantics>

</math><img src="./970d10ccb43641dae840b908612d11dfa0c53986.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.756ex; height:2.843ex;" alt="{\displaystyle w=\varphi (w)}" loading="lazy">—then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=\tau (w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=\tau (w)}</annotation>

</semantics>

</math><img src="./b19fb4adbf40d98fbc7a638d1d42691c0331de12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.864ex; height:2.843ex;" alt="{\displaystyle s=\tau (w)}" loading="lazy"> is a k-automatic sequence.<a href="#cite_note-AS175-6">[6]</a> Conversely, every k-automatic sequence is obtainable in this way.<a href="#cite_note-PF13-4">[4]</a> This result is due to <a href="Alan_Cobham_(mathematician)" title="Alan Cobham (mathematician)">Cobham</a>, and it is referred to in the literature as Cobham's little theorem.<a href="#cite_note-BLRS78-2">[2]</a><a href="#cite_note-C72-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="k-kernel">k-kernel</h3></div>

Let k ≥ 2. The k-kernel of the sequence s(n) is the set of subsequences

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}</annotation>

</semantics>

</math><img src="./89bcc4bdc8c15f7875f88a2bd7a67e9a0a0e8e6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.236ex; height:2.843ex;" alt="{\displaystyle K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}" loading="lazy"></dd></dl>

In most cases, the k-kernel of a sequence is infinite. However, if the k-kernel is finite, then the sequence s(n) is k-automatic, and the converse is also true. This is due to Eilenberg.<a href="#cite_note-AS185-8">[8]</a><a href="#cite_note-ApCOw527-9">[9]</a><a href="#cite_note-BR91-10">[10]</a>

It follows that a k-automatic sequence is necessarily a sequence on a finite alphabet.

<div class="mw-heading mw-heading3"><h3 id="Formal_power_series">Formal power series</h3></div>

Let u(n) be a sequence over an alphabet Σ and suppose that there is an <a href="Injective_function" title="Injective function">injective function</a> β from Σ to the <a href="Finite_field" title="Finite field">finite field</a> Fq, where q = pn for some prime p. The associated <a href="Formal_power_series" title="Formal power series">formal power series</a> is

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i\geq 0}\beta (u(i))X^{i}.}</annotation>

</semantics>

</math><img src="./c661de30de647b5a06c12574a87eb8e6169aeb91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:14.268ex; height:5.676ex;" alt="{\displaystyle \sum _{i\geq 0}\beta (u(i))X^{i}.}" loading="lazy"></dd></dl>

Then the sequence u is q-automatic if and only if this formal <a href="Power_series" title="Power series">power series</a> is <a href="Algebraic_function" title="Algebraic function">algebraic</a> over Fq(X). This result is due to Christol, and it is referred to in the literature as Christol's theorem.<a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Automatic sequences were introduced by <a href="Julius_Richard_B%C3%BCchi" title="Julius Richard Büchi">Büchi</a> in 1960,<a href="#cite_note-12">[12]</a> although his paper took a more logico-theoretic approach to the matter and did not use the terminology found in this article. The notion of automatic sequences was further studied by Cobham in 1972, who called these sequences "uniform <a href="Tag_system" title="Tag system">tag sequences</a>".<a href="#cite_note-C72-7">[7]</a>

The term "automatic sequence" first appeared in a paper of Deshouillers.<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

The following sequences are automatic:

<div class="mw-heading mw-heading3"><h3 id="Thue–Morse_sequence">Thue–Morse sequence</h3></div>

The <a href="Thue%E2%80%93Morse_sequence" title="Thue–Morse sequence">Thue–Morse sequence</a> t(n) (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A010060" class="extiw external" title="oeis:A010060">A010060</a>) is the <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed point</a> of the morphism 0 → 01, 1 → 10. Since the n-th term of the Thue–Morse sequence counts the number of ones <a href="Modulo_operation" class="mw-redirect" title="Modulo operation">modulo</a> 2 in the base-2 representation of n, it is generated by the two-state deterministic finite automaton with output pictured here, where being in state q0 indicates there are an even number of ones in the representation of n and being in state q1 indicates there are an odd number of ones.

Hence, the Thue–Morse sequence is 2-automatic.

<div class="mw-heading mw-heading3"><h3 id="Period-doubling_sequence">Period-doubling sequence</h3></div>

The n-th term of the period-doubling sequence d(n) (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A096268" class="extiw external" title="oeis:A096268">A096268</a>) is determined by the parity of the exponent of the highest power of 2 dividing n. It is also the fixed point of the morphism 0 → 01, 1 → 00.<a href="#cite_note-AS176-14">[14]</a> Starting with the initial term w = 0 and iterating the 2-uniform morphism φ on w where φ(0) = 01 and φ(1) = 00, it is evident that the period-doubling sequence is the fixed-point of φ(w) and thus it is 2-automatic.

<div class="mw-heading mw-heading3"><h3 id="Rudin–Shapiro_sequence">Rudin–Shapiro sequence</h3></div>

The n-th term of the <a href="Rudin%E2%80%93Shapiro_sequence" title="Rudin–Shapiro sequence">Rudin–Shapiro sequence</a> r(n) (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A020985" class="extiw external" title="oeis:A020985">A020985</a>) is determined by the number of consecutive ones in the base-2 representation of n. The 2-kernel of the Rudin–Shapiro sequence<a href="#cite_note-AS154-15">[15]</a> is

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}}</annotation>

</semantics>

</math><img src="./713b7898742149e5d192925c5781eb99156a3881.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.171ex; width:25.658ex; height:15.509ex;" alt="{\displaystyle {\begin{aligned}r(2n)&=r(n),\\r(4n+1)&=r(n),\\r(8n+7)&=r(2n+1),\\r(16n+3)&=r(8n+3),\\r(16n+11)&=r(4n+3).\end{aligned}}}" loading="lazy"></dd></dl>

Since the 2-kernel consists only of r(n), r(2n + 1), r(4n + 3), and r(8n + 3), it is finite and thus the Rudin–Shapiro sequence is 2-automatic.

<div class="mw-heading mw-heading3"><h3 id="Other_sequences">Other sequences</h3></div>

Both the <a href="Baum%E2%80%93Sweet_sequence" title="Baum–Sweet sequence">Baum–Sweet sequence</a><a href="#cite_note-AS156-16">[16]</a> (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A086747" class="extiw external" title="oeis:A086747">A086747</a>) and the <a href="Regular_paperfolding_sequence" title="Regular paperfolding sequence">regular paperfolding sequence</a><a href="#cite_note-BR92-17">[17]</a><a href="#cite_note-AS155-18">[18]</a><a href="#cite_note-LotIII526-19">[19]</a> (<a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="https://oeis.org/A014577" class="extiw external" title="oeis:A014577">A014577</a>) are automatic. In addition, the general paperfolding sequence with a periodic sequence of folds is also automatic.<a href="#cite_note-AS183-20">[20]</a>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

Automatic sequences exhibit a number of interesting properties. A non-exhaustive list of these properties is presented below.

<ul><li>Every automatic sequence is a <a href="Morphic_word" title="Morphic word">morphic word</a>.<a href="#cite_note-LotIII524-21">[21]</a></li>

<li>For k ≥ 2 and r ≥ 1, a sequence is k-automatic if and only if it is kr-automatic. This result is due to Eilenberg.<a href="#cite_note-22">[22]</a></li>

<li>For h and k <a href="Multiplicative_independence" title="Multiplicative independence">multiplicatively independent</a>, a sequence is both h-automatic and k-automatic if and only if it is ultimately periodic.<a href="#cite_note-as345-23">[23]</a> This result is due to Cobham also known as <a href="Cobham's_theorem" title="Cobham's theorem">Cobham's theorem</a>,<a href="#cite_note-24">[24]</a> with a multidimensional generalisation due to Semenov.<a href="#cite_note-25">[25]</a><a href="#cite_note-26">[26]</a></li>

<li>If u(n) is a k-automatic sequence over an alphabet Σ and f is a <a href="Uniform_morphism" class="mw-redirect" title="Uniform morphism">uniform morphism</a> from Σ∗ to another alphabet Δ∗, then f(u) is a k-automatic sequence over Δ.<a href="#cite_note-ApCoW532-27">[27]</a></li>

<li>If u(n) is a k-automatic sequence, then the sequences u(kn) and u(kn − 1) are ultimately periodic.<a href="#cite_note-ApCoW529-28">[28]</a> Conversely, if u(n) is an ultimately periodic sequence, then the sequence v defined by v(kn) = u(n) and otherwise zero is k-automatic.<a href="#cite_note-BR103-29">[29]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Proving_and_disproving_automaticity">Proving and disproving automaticity</h2></div>

Given a candidate sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(s_{n})_{n\geq 0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(s_{n})_{n\geq 0}}</annotation>

</semantics>

</math><img src="./ffa80fd89b077780d3150c6ae7461ebc0f42e1a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.626ex; height:2.843ex;" alt="{\displaystyle s=(s_{n})_{n\geq 0}}" loading="lazy">, it is usually easier to disprove its automaticity than to prove it. By the k-kernel characterization of k-automatic sequences, it suffices to produce infinitely many distinct elements in the k-kernel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{k}(s)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{k}(s)}</annotation>

</semantics>

</math><img src="./e0f1695743ee020f6f80f4f66452543fed7c1474.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.962ex; height:2.843ex;" alt="{\displaystyle K_{k}(s)}" loading="lazy"> to show that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> is not k-automatic. Heuristically, one might try to prove automaticity by checking the agreement of terms in the k-kernel, but this can occasionally lead to wrong guesses. For example, let

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=011010011\dots }</annotation>

</semantics>

</math><img src="./2f1c575df175fbb793cee02b687c58dfc4e4149d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:17.511ex; height:2.176ex;" alt="{\displaystyle t=011010011\dots }" loading="lazy"></dd></dl>

be the Thue–Morse word. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> be the word given by concatenating successive terms in the sequence of run-lengths of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> begins

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=12112221\dots .}</annotation>

</semantics>

</math><img src="./72960b3826e04a6b0cae797d68a6305d69bf6fff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:17.633ex; height:2.176ex;" alt="{\displaystyle s=12112221\dots .}" loading="lazy">.</dd></dl>

It is known that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> is the fixed point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h^{\omega }(1)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h^{\omega }(1)}</annotation>

</semantics>

</math><img src="./506a2cbfb6b3f0c582f28260fda0125c23ccad2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.565ex; height:2.843ex;" alt="{\displaystyle h^{\omega }(1)}" loading="lazy"> of the morphism

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(1)=121,h(2)=12221.}</annotation>

</semantics>

</math><img src="./b55e4d7cb638abd438cecac87c5026f8b58e7c9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.799ex; height:2.843ex;" alt="{\displaystyle h(1)=121,h(2)=12221.}" loading="lazy"></dd></dl>

The word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> is not 2-automatic, but certain elements of its 2-kernel agree for many terms. For example,

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134}</annotation>

</semantics>

</math><img src="./b4a06b6c5fab44d77982537b934d6200a523f505.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:36.044ex; height:2.509ex;" alt="{\displaystyle s_{16n+1}=s_{64n+1}{\text{ for }}0\leq n\leq 1864134}" loading="lazy">

but not for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1864135}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1864135}</annotation>

</semantics>

</math><img src="./e8d02ee85dc3e235c32902529ce24785e900ee54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.63ex; height:2.176ex;" alt="{\displaystyle n=1864135}" loading="lazy">.<a href="#cite_note-30">[30]</a>

Given a sequence that is conjectured to be automatic, there are a few useful approaches to proving it actually is. One approach is to directly construct a <a href="Deterministic_automaton" title="Deterministic automaton">deterministic automaton</a> with output that gives the sequence. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (s_{n})_{n\geq 0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s_{n})_{n\geq 0}}</annotation>

</semantics>

</math><img src="./94c4ace08527ce222b7f7e00ae0745bb45058b7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.437ex; height:2.843ex;" alt="{\displaystyle (s_{n})_{n\geq 0}}" loading="lazy"> written in the alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta }</annotation>

</semantics>

</math><img src="./32769037c408874e1890f77554c65f39c523ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.176ex;" alt="{\displaystyle \Delta }" loading="lazy">, and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n)_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n)_{k}}</annotation>

</semantics>

</math><img src="./5ced014b1e3d7d29a18792c6ceae44934df25e50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.293ex; height:2.843ex;" alt="{\displaystyle (n)_{k}}" loading="lazy"> denote the base-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> expansion of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Then the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(s_{n})_{n\geq 0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(s_{n})_{n\geq 0}}</annotation>

</semantics>

</math><img src="./ffa80fd89b077780d3150c6ae7461ebc0f42e1a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.626ex; height:2.843ex;" alt="{\displaystyle s=(s_{n})_{n\geq 0}}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-automatic if and only each of the fibres

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}}</annotation>

</semantics>

</math><img src="./396d5903281b1769109598a04924365606f6b6b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.185ex; height:2.843ex;" alt="{\displaystyle I_{k}(s,d):=\{(n)_{k}\mid s_{n}=d\}}" loading="lazy"></dd></dl>

is a regular language.<a href="#cite_note-31">[31]</a> Checking regularity of the fibres can often be done using the <a href="Pumping_lemma_for_regular_languages" title="Pumping lemma for regular languages">pumping lemma for regular languages</a>.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{k}(n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{k}(n)}</annotation>

</semantics>

</math><img src="./6d798465c21910c785357737ca826b4b1b2a9b6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.383ex; height:2.843ex;" alt="{\displaystyle s_{k}(n)}" loading="lazy"> denotes the sum of the digits in the base-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> expansion of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(X)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(X)}</annotation>

</semantics>

</math><img src="./f7425278aab7b6ceb8ddb54fa5ce71d2cf52d28f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.048ex; height:2.843ex;" alt="{\displaystyle p(X)}" loading="lazy"> is a polynomial with non-negative integer coefficients, and if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq 2}</annotation>

</semantics>

</math><img src="./c797a67c0a51167d373c013a9a020f4568a11754.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\geq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\geq 1}</annotation>

</semantics>

</math><img src="./1e0f3243e9d7f06bee548558bf20aaa9b5263d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.301ex; height:2.343ex;" alt="{\displaystyle m\geq 1}" loading="lazy"> are integers, then the sequence

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s_{k}(p(n)){\pmod {m}})_{n\geq 0}}</annotation>

</semantics>

</math><img src="./3899b246a5d8043e92d761153698bd9a00056764.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.215ex; height:2.843ex;" alt="{\displaystyle (s_{k}(p(n)){\pmod {m}})_{n\geq 0}}" loading="lazy"></dd></dl>

is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-automatic if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \deg p\leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \deg p\leq 1}</annotation>

</semantics>

</math><img src="./a3754f624eccba599cbb4af382bfcd4f1ad6bc39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.305ex; height:2.509ex;" alt="{\displaystyle \deg p\leq 1}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\mid k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\mid k-1}</annotation>

</semantics>

</math><img src="./2b0f48f642e0d5f923dc96eb9c5776ff34c492f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.192ex; height:2.843ex;" alt="{\displaystyle m\mid k-1}" loading="lazy">.<a href="#cite_note-32">[32]</a>

<div class="mw-heading mw-heading2"><h2 id="1-automatic_sequences">1-automatic sequences</h2></div>

k-automatic sequences are normally only defined for k ≥ 2.<a href="#cite_note-as1-1">[1]</a> The concept can be extended to k = 1 by defining a 1-automatic sequence to be a sequence whose n-th term depends on the <a href="Unary_numeral_system" title="Unary numeral system">unary notation</a> for n; that is, (1)n. Since a finite state automaton must eventually return to a previously visited state, all 1-automatic sequences are ultimately periodic.

<div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2></div>

Automatic sequences are robust against variations to either the definition or the input sequence. For instance, as noted in the automata-theoretic definition, a given sequence remains automatic under both direct and reverse reading of the input sequence. A sequence also remains automatic when an alternate set of digits is used or when the base is negated; that is, when the input sequence is represented in base −k instead of in base k.<a href="#cite_note-AS157-33">[33]</a> However, in contrast to using an alternate set of digits, a change of base may affect the automaticity of a sequence.

The domain of an automatic sequence can be extended from the natural numbers to the integers via two-sided automatic sequences. This stems from the fact that, given k ≥ 2, every integer can be represented uniquely in the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}</annotation>

</semantics>

</math><img src="./231704ec58ba4724825eac3dc4c5aabbd8313f87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:13.38ex; height:5.676ex;" alt="{\displaystyle \sum _{0\leq i\leq r}a_{i}(-k)^{i},}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}\in \{0,\dots ,k-1\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}\in \{0,\dots ,k-1\}}</annotation>

</semantics>

</math><img src="./7a8c2d59c8d1d180e4463508a4f1093ebbcb795e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.75ex; height:2.843ex;" alt="{\displaystyle a_{i}\in \{0,\dots ,k-1\}}" loading="lazy">. Then a two-sided infinite sequence a(n)n <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \in \mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \in \mathbb {Z} }</annotation>

</semantics>

</math><img src="./bf4280f3eac3f807374942067347c9219670bb81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.746ex; height:2.176ex;" alt="{\displaystyle \in \mathbb {Z} }" loading="lazy"> is (−k)-automatic if and only if its subsequences a(n)n ≥ 0 and a(−n)n ≥ 0 are k-automatic.<a href="#cite_note-AS162-34">[34]</a>

The alphabet of a k-automatic sequence can be extended from finite size to infinite size via <a href="K-regular_sequence" title="K-regular sequence">k-regular sequences</a>.<a href="#cite_note-35">[35]</a> The k-regular sequences can be characterized as those sequences whose k-kernel is finitely-generated. Every bounded k-regular sequence is automatic.<a href="#cite_note-36">[36]</a>

<div class="mw-heading mw-heading2"><h2 id="Logical_approach">Logical approach</h2></div>

For many 2-automatic sequences <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=(s_{n})_{n\geq 0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(s_{n})_{n\geq 0}}</annotation>

</semantics>

</math><img src="./ffa80fd89b077780d3150c6ae7461ebc0f42e1a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.626ex; height:2.843ex;" alt="{\displaystyle s=(s_{n})_{n\geq 0}}" loading="lazy">, the map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\mapsto s_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\mapsto s_{n}}</annotation>

</semantics>

</math><img src="./9f59d67c5dc4f9683b09268a2aec9f36070c2b1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.318ex; height:2.176ex;" alt="{\displaystyle n\mapsto s_{n}}" loading="lazy"> has the property that the first-order theory <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})}</annotation>

</semantics>

</math><img src="./aa71ee9572604c0c9c0a3fe05d8669d4f129bcf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.4ex; height:2.843ex;" alt="{\displaystyle {\text{FO}}(\mathbb {N} ,+,0,1,n\mapsto s_{n})}" loading="lazy"> is <a href="Decidability_(logic)" title="Decidability (logic)">decidable</a>. Since many non-trivial properties of automatic sequences can be written in <a href="First-order_logic" title="First-order logic">first-order logic</a>, it is possible to prove these properties mechanically by executing the decision procedure.<a href="#cite_note-37">[37]</a>

For example, the following properties of the Thue–Morse word can all be verified mechanically in this way:

<ul><li>The Thue–Morse word is overlap-free, i.e., it does not contain a word of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cxcxc}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cxcxc}</annotation>

</semantics>

</math><img src="./8d6c72b5723447c477e40e17ec4d6bdca30f7da3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.68ex; height:1.676ex;" alt="{\displaystyle cxcxc}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> is a single letter and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> is a possibly empty word.</li>

<li>A non-empty word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is bordered if there is a non-empty word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> and a possibly empty word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=wyw}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=wyw}</annotation>

</semantics>

</math><img src="./417eb710306f23f2668ba84b64294f8d5b7833f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.912ex; height:2.009ex;" alt="{\displaystyle x=wyw}" loading="lazy">. The Thue–Morse word contains a bordered factor for each length greater than 1.<a href="#cite_note-38">[38]</a></li>

<li>There is an unbordered factor of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> in the Thue–Morse word if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}</annotation>

</semantics>

</math><img src="./90419d47e4d976e4fad5f19aa1cd7e853725c418.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.208ex; height:2.843ex;" alt="{\displaystyle (n)_{2}\notin 1(01^{*}0)^{*}10^{*}1}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n)_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n)_{2}}</annotation>

</semantics>

</math><img src="./15db530ffca3137218b9c61ec39659adfde41411.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.258ex; height:2.843ex;" alt="{\displaystyle (n)_{2}}" loading="lazy"> denotes the binary representation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.<a href="#cite_note-39">[39]</a></li></ul>

The software Walnut,<a href="#cite_note-40">[40]</a><a href="#cite_note-41">[41]</a> developed by Hamoon Mousavi, implements a decision procedure for deciding many properties of certain automatic words, such as the Thue–Morse word. This implementation is a consequence of the above work on the logical approach to automatic sequences.

<ul><li><a href="B%C3%BCchi_arithmetic" title="Büchi arithmetic">Büchi arithmetic</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-as1-1">^ <a href="#cite_ref-as1_1-0">a</a> <a href="#cite_ref-as1_1-1">b</a> <a href="#cite_ref-as1_1-2">c</a> Allouche & Shallit (2003) p. 152

</li>

<li id="cite_note-BLRS78-2">^ <a href="#cite_ref-BLRS78_2-0">a</a> <a href="#cite_ref-BLRS78_2-1">b</a> Berstel et al (2009) p. 78

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Allouche & Shallit (2003) p. 168

</li>

<li id="cite_note-PF13-4">^ <a href="#cite_ref-PF13_4-0">a</a> <a href="#cite_ref-PF13_4-1">b</a> <a href="#cite_ref-PF13_4-2">c</a> Pytheas Fogg (2002) p. 13

</li>

<li id="cite_note-PF15-5"><a href="#cite_ref-PF15_5-0">^</a> Pytheas Fogg (2002) p. 15

</li>

<li id="cite_note-AS175-6"><a href="#cite_ref-AS175_6-0">^</a> Allouche & Shallit (2003) p. 175

</li>

<li id="cite_note-C72-7">^ <a href="#cite_ref-C72_7-0">a</a> <a href="#cite_ref-C72_7-1">b</a> Cobham (1972)

</li>

<li id="cite_note-AS185-8"><a href="#cite_ref-AS185_8-0">^</a> Allouche & Shallit (2003) p. 185

</li>

<li id="cite_note-ApCOw527-9"><a href="#cite_ref-ApCOw527_9-0">^</a> Lothaire (2005) p. 527

</li>

<li id="cite_note-BR91-10"><a href="#cite_ref-BR91_10-0">^</a> Berstel & Reutenauer (2011) p. 91

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChristol1979" class="citation journal cs1">Christol, G. (1979). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2879%2990011-2">"Ensembles presque périodiques k-reconnaissables"</a>. Theoret. Comput. Sci. 9: 141–145. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2879%2990011-2">10.1016/0304-3975(79)90011-2</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBüchi1990" class="citation book cs1">Büchi, J. R. (1990). "Weak Second-Order Arithmetic and Finite Automata". The Collected Works of J. Richard Büchi. Z. Math. Logik Grundlagen Math. Vol. 6. pp. 66–92. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4613-8928-6_22">10.1007/978-1-4613-8928-6_22</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4613-8930-9</bdi>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFDeshouillers1979–1980" class="citation journal cs1">Deshouillers, J.-M. (1979–1980). "La répartition modulo 1 des puissances de rationnels dans l'anneau des séries formelles sur un corps fini". Séminaire de Théorie des Nombres de Bordeaux: 5.01 – 5.22.</cite>

</li>

<li id="cite_note-AS176-14"><a href="#cite_ref-AS176_14-0">^</a> Allouche & Shallit (2003) p. 176

</li>

<li id="cite_note-AS154-15"><a href="#cite_ref-AS154_15-0">^</a> Allouche & Shallit (2003) p. 186

</li>

<li id="cite_note-AS156-16"><a href="#cite_ref-AS156_16-0">^</a> Allouche & Shallit (2003) p. 156

</li>

<li id="cite_note-BR92-17"><a href="#cite_ref-BR92_17-0">^</a> Berstel & Reutenauer (2011) p. 92

</li>

<li id="cite_note-AS155-18"><a href="#cite_ref-AS155_18-0">^</a> Allouche & Shallit (2003) p. 155

</li>

<li id="cite_note-LotIII526-19"><a href="#cite_ref-LotIII526_19-0">^</a> Lothaire (2005) p. 526

</li>

<li id="cite_note-AS183-20"><a href="#cite_ref-AS183_20-0">^</a> Allouche & Shallit (2003) p. 183

</li>

<li id="cite_note-LotIII524-21"><a href="#cite_ref-LotIII524_21-0">^</a> Lothaire (2005) p. 524

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFEilenberg1974" class="citation book cs1">Eilenberg, Samuel (1974). Automata, languages, and machines. Vol. A. Orlando: <a href="Academic_Press" title="Academic Press">Academic Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-122-34001-7</bdi>.</cite>

</li>

<li id="cite_note-as345-23"><a href="#cite_ref-as345_23-0">^</a> Allouche & Shallit (2003) pp. 345–350

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFCobham1969" class="citation journal cs1">Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01746527">10.1007/BF01746527</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19792434">19792434</a>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFSemenov1977" class="citation journal cs1 cs1-prop-foreign-lang-source">Semenov, A. L. (1977). "Presburgerness of predicates regular in two number systems". Sibirsk. Mat. Zh. (in Russian). 18 (2): 403–418. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1977SibMJ..18..289S">1977SibMJ..18..289S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00967164">10.1007/BF00967164</a>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFPointBruyère1997" class="citation journal cs1">Point, F.; <a href="V%C3%A9ronique_Bruy%C3%A8re" title="Véronique Bruyère">Bruyère, V.</a> (1997). "On the Cobham-Semenov theorem". Theory of Computing Systems. 30 (2): 197–220. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02679449">10.1007/BF02679449</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:31270341">31270341</a>.</cite>

</li>

<li id="cite_note-ApCoW532-27"><a href="#cite_ref-ApCoW532_27-0">^</a> Lothaire (2005) p. 532

</li>

<li id="cite_note-ApCoW529-28"><a href="#cite_ref-ApCoW529_28-0">^</a> Lothaire (2005) p. 529

</li>

<li id="cite_note-BR103-29"><a href="#cite_ref-BR103_29-0">^</a> Berstel & Reutenauer (2011) p. 103

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite id="CITEREFAlloucheAlloucheShallit2006" class="citation journal cs1">Allouche, G.; Allouche, J.-P.; Shallit, J. (2006). <a rel="nofollow" class="external text" href="http://www.numdam.org/item/AIF_2006__56_7_2115_0/">"Kolam indiens, dessins sur le sable aux îles Vanuatu, courbe de Sierpinski et morphismes de monoïde"</a>. Annales de l'Institut Fourier. 56 (7): 2126. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.5802%2Faif.2235">10.5802/aif.2235</a>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> Allouche and Shallit (2003) p. 160

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> Allouche and Shallit (2003) p. 197

</li>

<li id="cite_note-AS157-33"><a href="#cite_ref-AS157_33-0">^</a> Allouche & Shallit (2003) p. 157

</li>

<li id="cite_note-AS162-34"><a href="#cite_ref-AS162_34-0">^</a> Allouche & Shallit (2003) p. 162

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite id="CITEREFAlloucheShallit1992" class="citation journal cs1">Allouche, J.-P.; Shallit, J. (1992). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2892%2990001-v">"The ring of k-regular sequences"</a>. Theoret. Comput. Sci. 98 (2): 163–197. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2892%2990001-v">10.1016/0304-3975(92)90001-v</a>.</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFShallit" class="citation web cs1">Shallit, Jeffrey. <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf">"The Logical Approach to Automatic Sequences, Part 1: Automatic Sequences and k-Regular Sequences"</a> (PDF). Retrieved April 1, 2020.</cite>

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> <cite id="CITEREFShallit" class="citation web cs1">Shallit, J. <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/~shallit/Talks/linz1a.pdf">"The Logical Approach to Automatic Sequences: Part 1"</a> (PDF). Retrieved April 1, 2020.</cite>

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <cite id="CITEREFShallit" class="citation web cs1">Shallit, J. <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf">"The Logical Approach to Automatic Sequences: Part 3"</a> (PDF). Retrieved April 1, 2020.</cite>

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> <cite id="CITEREFShallit" class="citation web cs1">Shallit, J. <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/~shallit/Talks/linz3b.pdf">"The Logical Approach to Automatic Sequences: Part 3"</a> (PDF). Retrieved April 1, 2020.</cite>

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <cite id="CITEREFShallit" class="citation web cs1">Shallit, J. <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/~shallit/walnut.html">"Walnut Software"</a>. Retrieved April 1, 2020.</cite>

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> <cite id="CITEREFMousavi2016" class="citation arxiv cs1">Mousavi, H. (2016). "Automatic Theorem Proving in Walnut". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1603.06017">1603.06017</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.FL">cs.FL</a>].</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFAlloucheShallit2003" class="citation book cs1">Allouche, Jean-Paul; <a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, Jeffrey</a> (2003). Automatic Sequences: Theory, Applications, Generalizations. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-82332-6</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1086.11015">1086.11015</a>.</cite></li>

<li><cite id="CITEREFBerstelLauveReutenauerSaliola2009" class="citation book cs1">Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). <a rel="nofollow" class="external text" href="https://www.ams.org/bookpages/crmm-27">Combinatorics on words. Christoffel words and repetitions in words</a>. CRM Monograph Series. Vol. 27. Providence, RI: <a href="American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-4480-9</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1161.68043">1161.68043</a>.</cite></li>

<li><cite id="CITEREFBerstelReutenauer2011" class="citation book cs1">Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-19022-0</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1250.68007">1250.68007</a>.</cite></li>

<li><cite id="CITEREFCobham1972" class="citation journal cs1"><a href="Alan_Cobham_(mathematician)" title="Alan Cobham (mathematician)">Cobham, Alan</a> (1972). "Uniform tag sequences". <a href="Mathematical_Systems_Theory" class="mw-redirect" title="Mathematical Systems Theory">Mathematical Systems Theory</a>. 6 (1–2): 164–192. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01706087">10.1007/BF01706087</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:28356747">28356747</a>.</cite></li>

<li><cite id="CITEREFLothaire2005" class="citation book cs1"><a href="M._Lothaire" title="M. Lothaire">Lothaire, M.</a> (2005). <a rel="nofollow" class="external text" href="https://archive.org/details/appliedcombinato0000loth">Applied combinatorics on words</a>. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, <a href="Gesine_Reinert" title="Gesine Reinert">Gesine Reinert</a>, <a href="Sophie_Schbath" title="Sophie Schbath">Sophie Schbath</a>, Michael Waterman, Philippe Jacquet, <a href="Wojciech_Szpankowski" title="Wojciech Szpankowski">Wojciech Szpankowski</a>, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and <a href="Val%C3%A9rie_Berth%C3%A9" title="Valérie Berthé">Valérie Berthé</a>. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-84802-2</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1133.68067">1133.68067</a>.</cite></li>

<li><cite id="CITEREFPytheas_Fogg2002" class="citation book cs1">Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors <a href="Val%C3%A9rie_Berth%C3%A9" title="Valérie Berthé">Berthé, Valérie</a>; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-44141-0</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1014.11015">1014.11015</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFBerthéRigo2010" class="citation book cs1">Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-51597-9</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1197.68006">1197.68006</a>.</cite></li>

<li><cite id="CITEREFLoxton1988" class="citation book cs1">Loxton, J. H. (1988). "13. Automata and transcendence". In <a href="Alan_Baker_(mathematician)" title="Alan Baker (mathematician)">Baker, A.</a> (ed.). <a rel="nofollow" class="external text" href="https://archive.org/details/newadvancestrans1986bake">New Advances in Transcendence Theory</a>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/newadvancestrans1986bake/page/n113">215</a>–228. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-33545-4</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0656.10032">0656.10032</a>.</cite></li>

<li><cite id="CITEREFRowland2015" class="citation journal cs1">Rowland, Eric (2015). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fnoti1218">"What is ... an automatic sequence?"</a>. Notices of the American Mathematical Society. 62 (3): 274–276. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fnoti1218">10.1090/noti1218</a>.</cite></li>

<li><cite id="CITEREFShallit1999" class="citation book cs1"><a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, Jeffrey</a> (1999). "Number theory and formal languages". In <a href="Dennis_Hejhal" title="Dennis Hejhal">Hejhal, Dennis A.</a>; Friedman, Joel; <a href="Martin_Gutzwiller" title="Martin Gutzwiller">Gutzwiller, Martin C.</a>; <a href="Andrew_Odlyzko" title="Andrew Odlyzko">Odlyzko, Andrew M.</a> (eds.). Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15–26, 1996. The IMA volumes in mathematics and its applications. Vol. 109. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. pp. 547–570. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-98824-5</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-03" href="https://en.wikipedia.org/wiki/?title=Automatic_sequence&oldid=1298552767">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>